The amount of data in video signals is huge. A good video signal processing method is needed to encode/decode this data. MPEG is the most popular one. A conventional MPEG encoding system is illustrated in FIG. 1. Among the operations of video signal processing in such a system, motion estimation (ME) is the most time-consuming one. For instance, assuming that the minimum absolute error (MAE) cost function is used and a 16.times.16 block with a block matching of search range from +M to -M in both spatial directions, then there will be total 512.times.(2M+1).sup.2 addition operations for every motion vector generated. On the other hand, the total number of multiplications and additions required for a 16.times.16 block are about 4096, based on direct row-column matrix multiplication. The time required for Motion Estimation rapidly exceeds the time of Discrete Cosine Transform (DCT) for even moderate M. Note that this comparison does not consider the existence of more efficient DCT algorithms and high memory bandwidth which are required for ME operations. For more efficient encoding, M has to be as large as possible. Consequently, the ultimate bottleneck for real-time video encoding lies in the time-consuming motion estimation operation.
The known architectures for motion estimation in the literature can be divided into two classes. The first class is the ASIC array processor that utilizes regular and repetitive properties of ME operations. The second class is designed by optimizing the data path between different function blocks of general-purpose video signal processors (VSP). This patent adopts the general purpose approach for the consideration of programmability and practical implementation.
The typical video coder, as shown in FIG. 1, contains an input frame memory 12 for storing a current frame of video to be coded. The current frame of video is coded on a block-by-block basis. Some frames are coded in accordance with an intra-mode. In the intra-coding mode, no information from a previous frame is utilized and the coding relies entirely on information contained within the current frame. In the intra-mode, the current frame is divided into N.times.N pixel blocks, where N=16 for example. Each block of pixels is transmitted from the memory 12, via the multiplexer 14, to the Discrete Cosine Transform (DCT) circuit 16. In the DCT circuit 16, the Discrete Cosine Transform is applied to the block of pixels. The transformed pixels are then thresholded and quantized in the quantizer circuit 18. The quantized, transformed pixels are then coded using the variable length coder (VLC) 20. The variable length coded pixels are then transmitted via the multiplexer 22 to the buffer 24. The coded pixels are then transmitted from the buffer 24 via a channel 26 to a particular destination, where the pixels are decoded. Depending on the contents of the buffer 24, as well as depending on the transformed pixel values, the quantization controller 27 may vary the threshold and quantization stepsize utilized by the quantizer circuit 18. Information as to the threshold and quantization stepsize used to code a particular block is transmitted to the destination via line 23, the multiplexer 22, the buffer 24, and the channel 26.
The output of the quantizer circuit 18 is connected to the inverse quantizer circuit 28 and Inverse Discrete Cosine Transform (IDCT) circuit 29. These two circuits serve to reconstruct a block of pixels coded according to the intra-mode. The reconstructed block of pixels is stored in a previous frame memory system 30. Thus, on a block-by-block basis, the entire current frame, in reconstructed form, is stored in the previous frame memory system 30. This insures that when the next frame is coded, the immediately previously coded frame is always available. Note that when a block of pixels is coded using the intra-mode, the multiplexer 32 outputs zero so the adder 34 adds nothing to the output of the IDCT circuit 29. Thus, the output of the IDCT circuit 29 is connected directly to the previous frame memory system 30, without change. When a frame is coded in the intra-mode, all of the blocks in that frame are coded in the manner described above.
Some frames are coded using a technique known as predictive mode coding. When a frame is coded using the predictive mode, some blocks are coded using the intra-mode described above and some blocks are coded using an inter-mode described below. The inter-mode requires information from both the previous frame and the current frame. For a frame coded using the predictive mode, a decision as to whether to use the inter or intra-mode is made on a block-by-block basis.
The first step in deciding whether to use the intra-mode or the inter-mode for a current block is to first find the best match of the current block in the previous frame. For this purpose the processor circuit 300 is used. The processor circuit 300 contains a Motion Estimation Unit (MEU) 31, a Motion Compensation (MC) Decision Unit 32, and an Inter/Intra Decision Unit 33. The current block of the current frame is transmitted from the input frame memory 12 to the MEU 31. A search window of the previous frame, which previous frame is stored in the previous frame memory system 30, is also transmitted to the MEU circuit 31. The search window of the previous frame includes the pixels of the previous frame which correspond to the pixels of the current block of the current frame as well as additional pixels in each dimension to define a search window.
For example, the search window comprises the pixels in the previous frame which correspond to the 16.times.16 current block as well as .+-.7 pixels in each dimension. The error between the 16.times.16 current block and each possible 16.times.16 block in the search window is then determined. The error between the current block at each possible 16.times.16 block in the search window is determined according to the formula ##EQU1## where a(i,j) is a pixel from the current block, b(i-m,j-n) is a pixel from a specific block in the search window, and D=m,n is a displacement vector of the specific block in the search window with respect to a zero displacement block in the search window. The block in the search window which results in the minimum error is then determined. The block in the search window which results in the minimum error may be the zero displacement block (D=0,0) or a block which is displaced from the zero displacement block by a motion vector D=m*,n*, where m*,n*, is the value of m,n which results in the minimum error. The zero displacement block (i.e., D=0,0) in the search window is the 16.times.16 block which has the same location in the previous frame stored in the previous frame memory system 30 as the current block has in the current frame. If D does not equal 0,0, it means that the best match block in the search window is displaced from the zero displacement block by the motion vector m*,n*.
The MC decision unit 32 determines whether or not to use motion compensation for each current block in the current frame. The algorithm used to make the decision may be understood with help of FIG. 2. In FIG. 2, the vertical axis represents possible values of the error between the current block and the block in the search window which results in the minimum error. The horizontal axis represents possible values of the error between the current block and the D=0,0 block in the search window. The actual errors between the current block and the best match and zero displacement blocks of the search window define a point in the graph of FIG. 2. If this point is in the shaded region of FIG. 2 (excluding the decision curve) motion is detected and motion compensation is used for the current block. If the point is outside the shaded region, motion compensation is not used for the current block.
Once it is decided whether or not to use motion compensation for a current block, the Inter/Intra Decision Unit 33 decides whether to use intra-mode or inter-mode coding for the current block. If motion compensation is to be used, then the best match (i.e., minimum error) block of the search window is used for the inter/intra decision. If motion compensation is not used for the current block, then the inter/intra decision is made using the zero displacement block of the search window.
The inter/intra decision is as follows: the variance of the current block and the variance of the error between the current block and the best match or zero displacement block (depending on whether or not there is Motion Compensation) are determined. The variance (VAROR) of the current block is given by ##EQU2##
In addition, the variance of the error between current and best match block or zero displacement block is given by ##EQU3##
Depending on the value of VAROR and VAR, inter or intra mode coding is utilized in accordance with FIG. 3.
The decision as to whether to use inter or intra coding is transmitted from the MC circuit to the multiplexer 12 via line 35.
When intra-mode coding for the current block is used, the current block is transmitted from the frame memory 12, via the multiplexer 14, to the DCT circuit 16 and the block is coded directly using the DCT circuit 16, the quantizer 18, and the VLC circuit 20 in the manner discussed above. The inverse quantizer 28 and IDCT circuit 29 are used to reconstruct the block for storage in the previous frame memory 30.
When the inter-mode is used, the best match or zero displacement block (depending on whether or not Motion Compensation is used) from the previous frame is retrieved from the previous frame memory system 30 and is filtered by the loop filter 38, which filter performs a smoothing function. The subtractor 39 is then used to obtain the difference between the current block and best match or zero displacement block from the previous frame. The difference is then transmitted from the subtractor 39, via the multiplexer 14, to the DCT circuit 16. The difference is transformed using the DCT circuit 16. The resulting transform coefficients are then thresholded and quantized using the quantizer circuit 18. The resulting coefficients are coded using the VLC 20 and transmitted via the multiplexer 22, the buffer 24, and the channel 26 to a destination.
The difference is reconstructed using the inverse quantizer 28 and IDCT circuit 29.
When inter-mode coding is used, the output of the filter 38 is transmitted via the multiplexer 33 to the adder 34.
The adder 34 combines the reconstructed difference at the output of the IDCT circuit 29 with the output of the filter 38 to reconstruct the current block. The current block is then stored in the previous frame memory system 30.
There is also transmitted to the destination via line 35, multiplexer 22, buffer 24, and channel 26 an indication of whether inter or intra-mode coding is being used for a block. This indication is also transmitted to the multiplexer 14 so that the multiplexer can determine whether to transmit to the DCT circuit 16, the circuit block from the input frame memory 12 or the difference from the subtractor 39. In addition, there is transmitted to the destination, via line 36, the multiplexer 22, the buffer 24 and the channel 26, the best match displacement vector when motion compensation is being used or an indication that the zero displacement block from the search window is being used.
In a typical application, one frame is entirely intra-mode coded and the alternate frame is coded using a predictive mode in the manner described above.
An ideal ME core is required to efficiently perform various functions, including addition, subtraction, absolution and accumulation operations.
FIG. 4 illustrates a conventional ME core. The structure provides parallel adders 40, 41 for fast calculation of the absolute value. However, this core consumes a great deal of area because it requires two selectors (42,43), two adders (40,41) and two 1's complement circuits (46,47). One of the selectors can be eliminated at the expense of one more adder, as shown in FIG. 5 and disclosed by Goto et al., "250 MHz BiCMOS Super-High-Speed Video Signal Processor," IEEE JSSC, Dec. 1991, pp. 1876-1884.
FIG. 4 represents a conventional circuit for calculating the absolute value of two input signals. This calculation is necessary for motion compensation. The circuit consists of two input registers: X-register 44 and Y-register 45, a carry look ahead (CLA) adder (ADD1) 40 with invertors 46 and a selector (SEL1) 42 for the Y input, a second CLA adder (ADD2) 41 with inverters 47 for the X input, a pipeline register or latch 48 and a second selector (SEL 2) 43. Inputs X and Y are sent to the respective registers (44, 45). The first CLA adder 40 calculates either X+Y or X-Y by selecting Y or the inverse of Y with the selector 42. The X input is sent to inverter 47 so that the second CLA adder 41 always calculates Y-X. The results (X+Y, X-Y, Y-X) are sent to the latch 48 and then to the second selector 43. The second selector (SEL 2) 43 selects X+Y, X-Y and .vertline.X-Y.vertline. according to instructions. The critical count in first pipelined stage is 16 and the propagation delay time is 4.7 ns. A 250 Mhz operation cannot be realized using the circuit of FIG. 4.
The circuit of FIG. 5 was developed to do the calculations in 4 ns and to realize a 250 MHz operation. The circuit includes two input registers (50,51): (X-register and Y-register), three CLA adders (ADD1 52, ADD2 53, and ADD3 54), a logical operation unit (LU) 55, a pipeline register or latch 56, three overflow correctors (OC) 57, 58, 59, one selector (SEL) 60 and an output register 61. The third adder 54 was added so that X+Y and X-Y can be calculated by different adders, and, therefore, the extra selector FIG. 4 can be eliminated. The first adder 52 calculates X+Y from the inputs X and Y. The Y input is sent to inverter 100 before it is input to the second adder. The second adder 53 then calculates X-Y from the X input and inverted Y input. The X input is sent to inverter 101 before it is input to the third adder 54. The third adder then calculates Y-X from the Y input and inverted X input. Inputs X and Y are also sent to the logic unit 55. The results of the three adders and the logic unit are sent to a latch 56. Then X+Y is sent to overflow corrector 57, X-Y is sent to overflow corrector 58, and Y-X is sent to overflow corrector 59. After the signals are corrected for overflow, a selector 60 selects either X+Y, X-Y,.vertline.X-Y.vertline. or a logic operation result to send to the output register 61. The critical gate count is 14 gate and the carry propagation delay time of three adders is improved. The hardware size for X-Y, X+Y and Y-X has become 1.3 times as large as FIG. 4, the critical path gate count and propagation delay time are reduced.
Another conventional core is shown in FIG. 6 and disclosed by Kikuchi et al., "A Single-Chip 16-bit 25-ns Real Time Video/Image Signal Processor," IEEE JSSC, Dec. 1989, pp. 1662-1667. FIG. 6 illustrates another known system for calculating the absolute value of two input signals. The circuit includes two registers 62, 64 and one adder (ADD) 65. An inverter 63 is used for the Y-input signal. A second inverter 66 is used to obtain Y-X. An incrementor (+1) 67 is used to increment its input data by plus one and results in X-Y. An absolute value .vertline.Y-X.vertline. can be selected by the selector (SEL) 68. This circuit reduces hardware size but increases the propagation delay. This core provides relatively efficient hardware for absolute operation only, but it still requires two adders and one selector.
Moreover, all the above mentioned conventional designs do not include an accumulator for obtaining a total sum of these absolute differences. They do not take advantage of the correlation between the adder for absolute value calculation and accumulation.